package com.yanceysong.codetop.s91_s100;

import com.yanceysong.common.ListNode;

public class S96_Easy_83_删除排序链表中的重复元素 {
    /**
     * .S96_Easy_83_删除排序链表中的重复元素
     * .<p>
     * .<a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-list/">...</a>
     * .<p>
     * .给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
     * .<p>
     * .示例：
     * .<p>
     * .输入：head = [1,1,2]
     * .输出：[1,2]
     * .<p>
     * .输入：head = [1,1,2,3,3]
     * .输出：[1,2,3]
     * .<p>
     * .提示：
     * .<p>
     * .链表中节点数目在范围 [0, 300] 内
     * .-100 <= Node.val <= 100
     * .题目数据保证链表已经按升序排列
     * .<p>
     * .核心标签：链表、双指针
     * .<p>
     * .算法原理：一次遍历删除重复节点
     * .- 由于链表已经排序，相同的元素必定相邻
     * .- 使用一个指针遍历链表，比较当前节点和下一个节点的值
     * .- 如果值相同，跳过下一个节点（删除重复节点）
     * .- 如果值不同，移动指针到下一个节点
     * .- 继续遍历直到链表末尾
     * .<p>
     * .关键洞察：
     * .1. 链表已排序，重复元素必定相邻，无需额外的数据结构
     * .2. 只需要保留每组重复元素中的第一个节点
     * .3. 通过修改 next 指针即可删除节点，无需实际释放内存（Java有GC）
     * .4. 不需要虚拟头节点，因为头节点永远不会被删除（它是第一个出现的）
     * .<p>
     * .图解示例：head = [1,1,2,3,3]
     * .<p>
     * .初始状态：
     * .current → 1 → 1 → 2 → 3 → 3 → null
     * .<p>
     * .步骤1：current.val (1) == current.next.val (1)，删除重复节点
     * .current → 1 ┐
     * .↓     X  1  ↓
     * .└────────→ 2 → 3 → 3 → null
     * .<p>
     * .步骤2：current.val (1) != current.next.val (2)，移动指针
     * .1 → current → 2 → 3 → 3 → null
     * .<p>
     * .步骤3：current.val (2) != current.next.val (3)，移动指针
     * .1 → 2 → current → 3 → 3 → null
     * .<p>
     * .步骤4：current.val (3) == current.next.val (3)，删除重复节点
     * .1 → 2 → current → 3 ┐
     * .↓     X  3  ↓
     * .└────────→ null
     * .<p>
     * .步骤5：current.next == null，遍历结束
     * .1 → 2 → 3 → null
     * .<p>
     * .详细过程图解：
     * .<p>
     * .原始链表：1 → 1 → 2 → 3 → 3 → null
     * .<p>
     * .第1次循环：
     * .cur
     * .↓
     * .1 → 1 → 2 → 3 → 3 → null
     * .cur.val == cur.next.val (1 == 1)
     * .执行：cur.next = cur.next.next
     * .结果：1 ───→ 2 → 3 → 3 → null
     * .<p>
     * .第2次循环：
     * .cur
     * .↓
     * .1 ───→ 2 → 3 → 3 → null
     * .cur.val != cur.next.val (1 != 2)
     * .执行：cur = cur.next
     * .结果：1 → 2 → 3 → 3 → null
     * .cur
     * .<p>
     * .第3次循环：
     * .cur
     * .↓
     * .1 → 2 → 3 → 3 → null
     * .cur.val != cur.next.val (2 != 3)
     * .执行：cur = cur.next
     * .结果：1 → 2 → 3 → 3 → null
     * .cur
     * .<p>
     * .第4次循环：
     * .cur
     * .↓
     * .1 → 2 → 3 → 3 → null
     * .cur.val == cur.next.val (3 == 3)
     * .执行：cur.next = cur.next.next
     * .结果：1 → 2 → 3 ───→ null
     * .cur
     * .<p>
     * .第5次循环：
     * .cur.next == null，退出循环
     * .<p>
     * .最终结果：1 → 2 → 3 → null
     * .<p>
     * .另一个示例：head = [1,1,1]
     * .<p>
     * .初始：current → 1 → 1 → 1 → null
     * .<p>
     * .步骤1：1 == 1，删除
     * .current → 1 ───→ 1 → null
     * .<p>
     * .步骤2：1 == 1，删除
     * .current → 1 ───────→ null
     * .<p>
     * .结果：1 → null
     * .<p>
     * .时间复杂度：O(n)，其中 n 为链表长度
     * .- 需要遍历链表一次，每个节点最多访问一次
     * .<p>
     * .空间复杂度：O(1)
     * .- 只使用了常数个指针变量，没有使用额外的数据结构
     */
    public ListNode deleteDuplicates(ListNode head) {
        // 边界条件检查：空链表直接返回
        if (head == null) {
            return head;
        }

        // 使用 current 指针遍历链表
        ListNode current = head;

        // 遍历链表，直到当前节点的下一个节点为空
        while (current.next != null) {
            // 如果当前节点的值等于下一个节点的值（发现重复）
            if (current.val == current.next.val) {
                // 删除下一个节点：将当前节点的 next 指针指向下下个节点
                // 这样就跳过了重复的节点
                current.next = current.next.next;
                // 注意：这里不移动 current 指针，因为可能有连续多个重复值
                // 例如：1 → 1 → 1，需要连续删除
            } else {
                // 如果值不同，移动指针到下一个节点
                current = current.next;
            }
        }

        // 返回处理后的链表头节点
        return head;
    }

    public static void main(String[] args) {
        S96_Easy_83_删除排序链表中的重复元素 solution = new S96_Easy_83_删除排序链表中的重复元素();

        System.out.println("=== 删除排序链表中的重复元素测试开始 ===");

        // 测试1: 题目示例1 - [1,1,2]
        System.out.println("\n--- 测试1: [1,1,2] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - [1,1,2,3,3]
        System.out.println("\n--- 测试2: [1,1,2,3,3] ---");
        testCase2(solution);

        // 测试3: 空链表
        System.out.println("\n--- 测试3: 空链表 ---");
        testEmptyList(solution);

        // 测试4: 单节点链表
        System.out.println("\n--- 测试4: 单节点链表 [1] ---");
        testSingleNode(solution);

        // 测试5: 所有元素都相同
        System.out.println("\n--- 测试5: 所有元素都相同 [1,1,1,1,1] ---");
        testAllSame(solution);

        // 测试6: 没有重复元素
        System.out.println("\n--- 测试6: 没有重复元素 [1,2,3,4,5] ---");
        testNoDuplicates(solution);

        // 测试7: 两个节点，相同值
        System.out.println("\n--- 测试7: 两个节点，相同值 [1,1] ---");
        testTwoNodesSame(solution);

        // 测试8: 两个节点，不同值
        System.out.println("\n--- 测试8: 两个节点，不同值 [1,2] ---");
        testTwoNodesDifferent(solution);

        // 测试9: 多组重复元素
        System.out.println("\n--- 测试9: 多组重复元素 [1,1,2,2,3,3] ---");
        testMultipleGroups(solution);

        // 测试10: 重复在开头
        System.out.println("\n--- 测试10: 重复在开头 [1,1,1,2,3] ---");
        testDuplicatesAtStart(solution);

        // 测试11: 重复在末尾
        System.out.println("\n--- 测试11: 重复在末尾 [1,2,3,3,3] ---");
        testDuplicatesAtEnd(solution);

        // 测试12: 负数和零
        System.out.println("\n--- 测试12: 负数和零 [-3,-1,0,0,0,3,3] ---");
        testNegativeAndZero(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: [1,1,2]
     * .期望输出：[1,2]
     */
    private static void testCase1(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);

        System.out.println("输入: 1 → 1 → 2 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 2 → null)");

        assert result.val == 1 : "第一个节点应该是1";
        assert result.next.val == 2 : "第二个节点应该是2";
        assert result.next.next == null : "应该只有两个节点";

        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: [1,1,2,3,3]
     * .期望输出：[1,2,3]
     */
    private static void testCase2(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(3);

        System.out.println("输入: 1 → 1 → 2 → 3 → 3 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 2 → 3 → null)");

        assert result.val == 1 : "第一个节点应该是1";
        assert result.next.val == 2 : "第二个节点应该是2";
        assert result.next.next.val == 3 : "第三个节点应该是3";
        assert result.next.next.next == null : "应该只有三个节点";

        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 空链表
     * .期望输出：null
     */
    private static void testEmptyList(S96_Easy_83_删除排序链表中的重复元素 solution) {
        System.out.println("输入: null");
        ListNode result = solution.deleteDuplicates(null);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: null)");

        assert result == null : "空链表应该返回null";

        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 单节点链表 [1]
     * .期望输出：[1]
     */
    private static void testSingleNode(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);

        System.out.println("输入: 1 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → null)");

        assert result.val == 1 : "节点值应该是1";
        assert result.next == null : "应该只有一个节点";

        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 所有元素都相同 [1,1,1,1,1]
     * .期望输出：[1]
     */
    private static void testAllSame(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(1);
        head.next.next.next.next = new ListNode(1);

        System.out.println("输入: 1 → 1 → 1 → 1 → 1 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → null)");

        assert result.val == 1 : "节点值应该是1";
        assert result.next == null : "应该只有一个节点";

        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 没有重复元素 [1,2,3,4,5]
     * .期望输出：[1,2,3,4,5]
     */
    private static void testNoDuplicates(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.println("输入: 1 → 2 → 3 → 4 → 5 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 2 → 3 → 4 → 5 → null)");

        ListNode current = result;
        for (int i = 1; i <= 5; i++) {
            assert current != null : "节点不应该为null";
            assert current.val == i : "节点值应该是" + i;
            current = current.next;
        }
        assert current == null : "应该只有5个节点";

        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 两个节点，相同值 [1,1]
     * .期望输出：[1]
     */
    private static void testTwoNodesSame(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);

        System.out.println("输入: 1 → 1 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → null)");

        assert result.val == 1 : "节点值应该是1";
        assert result.next == null : "应该只有一个节点";

        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 两个节点，不同值 [1,2]
     * .期望输出：[1,2]
     */
    private static void testTwoNodesDifferent(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);

        System.out.println("输入: 1 → 2 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 2 → null)");

        assert result.val == 1 : "第一个节点应该是1";
        assert result.next.val == 2 : "第二个节点应该是2";
        assert result.next.next == null : "应该只有两个节点";

        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 多组重复元素 [1,1,2,2,3,3]
     * .期望输出：[1,2,3]
     */
    private static void testMultipleGroups(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(3);
        head.next.next.next.next.next = new ListNode(3);

        System.out.println("输入: 1 → 1 → 2 → 2 → 3 → 3 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 2 → 3 → null)");

        assert result.val == 1 : "第一个节点应该是1";
        assert result.next.val == 2 : "第二个节点应该是2";
        assert result.next.next.val == 3 : "第三个节点应该是3";
        assert result.next.next.next == null : "应该只有三个节点";

        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 重复在开头 [1,1,1,2,3]
     * .期望输出：[1,2,3]
     */
    private static void testDuplicatesAtStart(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(3);

        System.out.println("输入: 1 → 1 → 1 → 2 → 3 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 2 → 3 → null)");

        assert result.val == 1 : "第一个节点应该是1";
        assert result.next.val == 2 : "第二个节点应该是2";
        assert result.next.next.val == 3 : "第三个节点应该是3";
        assert result.next.next.next == null : "应该只有三个节点";

        System.out.println("✓ 测试10通过");
    }

    /**
     * .测试11: 重复在末尾 [1,2,3,3,3]
     * .期望输出：[1,2,3]
     */
    private static void testDuplicatesAtEnd(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(3);

        System.out.println("输入: 1 → 2 → 3 → 3 → 3 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: 1 → 2 → 3 → null)");

        assert result.val == 1 : "第一个节点应该是1";
        assert result.next.val == 2 : "第二个节点应该是2";
        assert result.next.next.val == 3 : "第三个节点应该是3";
        assert result.next.next.next == null : "应该只有三个节点";

        System.out.println("✓ 测试11通过");
    }

    /**
     * .测试12: 负数和零 [-3,-1,0,0,0,3,3]
     * .期望输出：[-3,-1,0,3]
     */
    private static void testNegativeAndZero(S96_Easy_83_删除排序链表中的重复元素 solution) {
        ListNode head = new ListNode(-3);
        head.next = new ListNode(-1);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(0);
        head.next.next.next.next = new ListNode(0);
        head.next.next.next.next.next = new ListNode(3);
        head.next.next.next.next.next.next = new ListNode(3);

        System.out.println("输入: -3 → -1 → 0 → 0 → 0 → 3 → 3 → null");
        ListNode result = solution.deleteDuplicates(head);
        System.out.print("输出: ");
        printList(result);
        System.out.println(" (期望: -3 → -1 → 0 → 3 → null)");

        assert result.val == -3 : "第一个节点应该是-3";
        assert result.next.val == -1 : "第二个节点应该是-1";
        assert result.next.next.val == 0 : "第三个节点应该是0";
        assert result.next.next.next.val == 3 : "第四个节点应该是3";
        assert result.next.next.next.next == null : "应该只有四个节点";

        System.out.println("✓ 测试12通过");
    }

    /**
     * .辅助方法：打印链表
     */
    private static void printList(ListNode head) {
        if (head == null) {
            System.out.print("null");
            return;
        }

        ListNode current = head;
        while (current != null) {
            System.out.print(current.val);
            if (current.next != null) {
                System.out.print(" → ");
            }
            current = current.next;
        }
        System.out.print(" → null");
    }
}

